All Questions
6 questions
2votes
0answers
145views
Counterexample for the 1-optimal matching algorithm in Gabow's and Tarjan's paper on scaling algorithms for networks
Context I am reading Faster scaling algorithms for network problems by Gabow and Tarjan where I am researching part 2: "Matching and extensions". However, I am a bit confused with the ...
- 21
6votes
1answer
93views
Generate cut $(A,B)$ in edge-colored graph $(V,E_1 \cup E_2)$ such that there are more red than white crossings, i.e $|E_1(A,B)| > |E_2(A,B)|$
Let $G=(V,E)$ be graph. Recall that a cut of $G$ is (or can uniquely be identified with) a pair $(A,B)$ of nonempty subsets of $V$ which partition it. Given a cut $(A,B)$, let $E(A,B) := \{(a,b) \in ...
- 291
3votes
1answer
249views
How is SDP an extension of spectral algorithms?
In one of his lectures, Uri Feige described semidefinite programming (SDP) as ... an algorithmic technique that extends both linear programming and spectral algorithms. I know the basic definition ...
- 630
2votes
1answer
272views
H-representation of convex hull
Consider a set of polytopes $P_j\;\;j=1,2,\dots,r$ with the same structure as follows: $P_j=\Big\{(x_{j1},\dots, x_{jt})\Big| \sum_{i=1}^t x_{ji}=1, x_{ji}\in [a_{ji},b_{ji}]\subseteq [0,1]\Big\}$ ...
- 253
1vote
1answer
331views
Approximation algorithm for graph problem
In the process of trying to create an approximation algorithm for the following problem. Let $G = (V,E)$ be a graph, $c_e, c_{iv} \ge 0$, for $e \in E$, $i \in L$, and $v \in V$, where $L$ is a ...
- 233
0votes
1answer
3kviews
Linear Programming with Modulo Linear Constraints
Given $G = (V,E)$ I can formulate a relaxation of graph $K$-coloring as: find feasible point s.t. $\min \sum_{ij}v_{ij}$ for all $(i,j)$ in $E$ $z_{ij} \le (c_i - c_j) \bmod k$ (i) $z_{ij} \le (...
- 745
